package com.demo.algorithm.bfs03;


import com.demo.algorithm.common.TreeNode;
//import com.google.common.collect.EvictingQueue;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Description: BFS——二叉树最小深度 （LeetCode111）
 *
 * @Date: 2021/6/3 23:33
 * @Author: zsyoung@qq.com
 */
public class TreeNodeMinDepth {

    private static int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int depth = 1;

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                /*判断是否达到终点*/
                if (cur.left == null && cur.right == null) {
                    return depth;
                }
                /*如果没有达到终点，就加入周围的节点*/
                if (cur.left != null) {
                    q.offer(cur.left);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
            }
            depth++;
        }
        return depth;
    }

    /**
     * 测试两个先进先出的队列
     */
    private static void test() {
//        EvictingQueue<String> q = new EvictingQueue<String>(3);
//        EvictingQueue<String> queue = EvictingQueue.create(3);
//        queue.add("qqq");
//        queue.add("sss");
//        queue.add("www");
//        queue.add("rrr");
//        System.out.println("queue.size() = " + queue.size());
//        System.out.println("queue = " + queue);

//        CircularFifoQueue<String> queue = new CircularFifoQueue<>(2);
//        System.out.println("queue.size() = " + queue.size());
//        queue.add("qqq");
//        queue.add("sss");
//        queue.add("www");
//        queue.add("rrr");
//        System.out.println("queue = " + queue);
    }

    public static void main(String[] args) {
        String str = "[3,9,20,null,null,15,7]";
        TreeNode node = TreeNode.mkTree(str);
        System.out.println("minDepth(node) = " + minDepth(node));
        test();
    }
}
